As integrated circuits have increased in complexity and as there has developed a need for integrated circuits customized to a particular application, computer-aided design (CAD) has become an important technology. Moreover, to achieve fast turn around time in the design phase, an important technique in CAD has been logic synthesis for the design of integrated circuits. In this technique, the digital circuit to perform a specific application is first synthesized in block schematic form as an assembly of functional elements, such as AND and OR gates, and memory elements, such as registers. Various computer programs are available for this process.
While this approach can provide fast turn around times and a circuit that is usually efficient in its use of surface area and that also lends itself readily to testing, the circuit is often not especially high in performance, typically because it usually includes unnecessarily long paths that serve to slow the speed of the circuit. The slower the speed of a circuit, the longer the clock period that needs to be used with the circuit, and the slower the rate at which the circuit can perform the processing. Generally, a technique for improving the performance of an integrated circuit synthesized in this manner is subsequently to modify the circuit specifically to shorten the paths thereof that introduce long delays.
The bulk of the work done in the area of performance optimization of digital circuits has focused on combinational logic circuits which are circuits, free of memory elements, such as registers, that make a circuit dependent on its prior history. Circuits that include such memory elements are generally described as sequential circuits. While recognizing the fact that these prior techniques vary significantly in terms of their approaches towards the problem of designing faster combinational logic circuits, we will collectively classify them as being combinational speedup or combinational resynthesis techniques to recognize the fact that they focus on combinational logic circuits. Combinational speedup techniques have been directly applied to sequential logic circuits by considering the combinational part between the memory elements; a speedup of the combinational part can directly translate into a reduction of the clock period. However, this approach does not exploit any information derived from the sequential behavior of the circuit. An alternative approach, termed retiming is described in the paper entitled "Optimizing Synchronous circuitry by Retiming", published in Advanced Research in VLSI: Proceedings of the Third Caltech Conference, pp. 23-36, Computer Science Press, 1983. This approach recognizes the sequential behavior of the circuit and attempts to minimize the clock period of the circuit by repositioning the memory elements. Combinational speedup and retiming can be viewed as two ends of the spectrum; combinational speedup works only on the combinational logic and ignores the memory elements, retiming focuses only on the memory elements and ignores the nature of the combinational logic. This naturally led to work that attempted to combine the two ends of this spectrum. In the approach termed retiming and resynthesis, as described in the paper entitled "Retiming and Resynthesis: Optimizing Sequential Networks With Combinational Techniques", published in IEEE Transactions on Computer-Aided Design, Vol. CAD-10 No. 1, pp. 74-84, January, 1991, it was shown how the two could be combined for a restricted class of sequential circuits. Subsequently, in a paper entitled "Performance Optimization of Pipelined Circuits", published in Proceedings of the International Conference on Computer-Aided Design, November, 1990, pp. 410-413, it was demonstrated how retiming and resynthesis could be optimally combined for the performance optimization of pipelined circuits. The most notable limitation of this approach was the restriction on the class of circuits that could be handled.